class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        ret=0
        def traverse(offset,total):
            nonlocal ret
            if offset>=len(nums):
                if total==S:
                    ret+=1
                return 
            traverse(offset+1,total+nums[offset])
            traverse(offset+1,total-nums[offset])
        traverse(0,0)
        return ret

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        dp=[[0]*2001 for _ in range(len(nums))]
        dp[0][nums[0]+1000]+=1
        dp[0][-nums[0]+1000]+=1
        for i in range(1,len(nums)):
            for j in range(2000):
                if dp[i-1][j]>0:
                    dp[i][j+nums[i]]+=dp[i-1][j]
                    dp[i][j-nums[i]]+=dp[i-1][j]
        return 0 if S>1000 else dp[-1][S+1000]